// 解题思路：
// 题目要求合并区间，即求并集
// 经验：区间问题，通常需要对区间进行排序（按照区间左端点或区间右端点）
// 按照区间左端点进行排序
// 将第一个区间作为基准区间，遍历后面的区间，如果基准区间的右端点 right >= intervals[i][0]，就表示区间有重合，可以合并
// 合并就是取区间右端点的最大值，right = Math.max(right, intervals[i][1])
// 如果基准区间的右端点 right < intervals[i][0]，表示区间没有重合，可以收集当前基准区间作为结果
// 直到遍历完最后一个区间，还差最后这个区间没有收集，再单独收集以下，返回收集的结果即可

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int n = intervals.length;
        if(n == 1) return intervals;

        List<int[]> ret = new ArrayList<>();
        int left = intervals[0][0]; int right = intervals[0][1];

        int i = 1;
        while(i < n){
            if(intervals[i][0] <= right){
                right = Math.max(right, intervals[i][1]);
            }else{
                ret.add(new int[] {left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
            i++;
        }
        ret.add(new int[] {left, right});

        return ret.toArray(new int[0][]);
    }
}
